package P94.P102;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author DJ同学
 * @Date 2021/2/22 22:54
 * @Version 1.0
 * @Name 二叉树的层序遍历 获得层数
 * @Problem
 * @Idea BFS 层数
 */
public class Solution3 {
    @Test
    public void test01(){
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.left.left = null;
        root.left.right = null;
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.left.left = null;
        root.right.left.right = null;
        root.right.right = new TreeNode(7);
        root.right.right.left = null;
        root.right.right.right = null;
        Integer level = levelOrder(root);
        System.out.println(level);//3
    }
    public Integer levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int cnt=0;
        while(!queue.isEmpty()){
            //获得当前层的数量
            int cnt1 = queue.size();
            //for一次 弹出当前层的节点
            for(int i = 0;i<cnt1;i++){
                TreeNode cur = queue.peek();
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                //弹出当前节点
                queue.poll();
            }
            cnt++;
        }
        return cnt;
    }
}
